#include <bits/stdc++.h>

constexpr int P = int(1e9) + 7;
constexpr int N = int(1e6);

int mu[N + 1];
int pw[N + 1];
int sigma[N + 1];
bool np[N + 1];
std::vector<int> pri;

int sum_sig[N + 1];
int F[N + 1];
int G[N + 1];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    mu[1] = 1;
    sigma[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!np[i]) {
            pri.push_back(i);
            mu[i] = -1;
            pw[i] = i;
            sigma[i] = i + 1;
        }
        for (int j : pri) {
            int k = i * j;
            if (k > N) break;
            np[k] = true;
            if (i % j != 0) {
                mu[k] = -mu[i];
                pw[k] = j;
                sigma[k] = sigma[i] * (j + 1);
            } else {
                mu[k] = 0;
                pw[k] = pw[i] * j;
                if (k == pw[k]) {
                    sigma[k] = sigma[i] + pw[i] * j;
                } else{
                    sigma[k] = sigma[i / pw[i]] * sigma[pw[i] * j];
                }
                break;
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        sum_sig[i] = (sum_sig[i - 1] + sigma[i]) % P;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i; j <= N; j += i) {
            int k = j / i;
            int mu_d2 = 1ll * (mu[i] + P) % P * i % P * i % P;
            F[j] = (F[j] + 1ll * mu_d2 * k % P * sigma[k] % P * sum_sig[k]) % P;
            G[j] = (G[j] + 1ll * mu_d2 * k % P * sigma[k] % P * sigma[k]) % P;
        }
    }
    for (int i = 1; i <= N; ++i) {
        F[i] = (F[i] + F[i - 1]) % P;
        G[i] = (G[i] + G[i - 1]) % P;
    }

    int T;
    std::cin >> T;
    for (int _ = 1; _ <= T; ++_) {
        int n;
        std::cin >> n;
        std::cout << "Case #" << _ << ": " << (2ll * F[n] - G[n] + P) % P << '\n';
    }


    return 0;
}